// -----------------------------
// projects/c++/collatz/main.c++
// Copyright (C) 2009
// Glenn P. Downing
// -----------------------------

/*
 To run the tests:
 % g++ -ansi -pedantic -lcppunit -ldl -Wall -DTEST main.c++ -o main.app
 % valgrind main.app
 
 To run the program:
 % g++ -ansi -pedantic -Wall main.c++ -o main.app
 % valgrind main.app < Collatz.in > Collatz.out
 
 To configure Doxygen:
 doxygen -g
 That creates the file Doxyfile.
 Make the following edits:
 EXTRACT_ALL            = YES
 EXTRACT_PRIVATE        = YES
 EXTRACT_STATIC         = YES
 GENERATE_LATEX         = NO
 
 To document the program:
 doxygen Doxyfile
 */

// --------
// includes
// --------

#include <cassert>  // assert
#include <iostream> // cin, cout, endl, ios_base, istream, ostream

#ifdef TEST
#include "cppunit/TestSuite.h"      // TestSuite
#include "cppunit/TextTestRunner.h" // TestRunner
#endif // TEST

// -------
// defines
// -------

#ifdef ONLINE_JUDGE
#define NDEBUG
#endif

// -------
// globals
// -------

#ifdef TEST
int PRIME_MAX = 5200001;
#else
const int PRIME_MAX = 5200001;
#endif

// array of primality. O-index, so if isPrime[n] = true, then n+1 is prime
//                                 if isPrime[n] = false, then n+1 is composite
bool isPrime[PRIME_MAX]; //= { true };
int sum;
int addend[4];

// ----
// read
// ----

/**
 * reads an int into sum
 * @return true if that succeeds, false otherwise
 */
bool read (std::istream& in) {
    if (!(in >> sum))
        return false;
    return true;
}

// -----
// print
// -----

/**
 * prints the values of i, j, and v
 */
void print (std::ostream& out) {
    out << addend[0] << " " << addend[1] << " " << addend[2] << " " << addend[3] << std::endl;}

// ---------
// nextPrime
// ---------

inline int nextPrime(int n) {
    int nextPrime = n + 1;
    for (; !isPrime[nextPrime] && nextPrime < PRIME_MAX; nextPrime++);

    if (nextPrime >= PRIME_MAX) return -1;
    return nextPrime;
}

// ----
// eval
// ----

int eval() {

    addend[0] = 1;

    while(addend[0] != -1) {

        addend[0] = nextPrime(addend[0]);
        if (addend[0] == -1) break;

        if ((sum - addend[0]) % 2 == 0) { addend[1] = 1; }  // will be inc. to 2
        else { addend[1] = 2; }                             // will be inc. to 3

        while (addend[1] != -1) {
            addend[1] = nextPrime(addend[1]);
            if (addend[1] == -1) break;

            addend[0] = 2;

            int partialSum = sum - addend[0] - addend[1];
            addend[2] = 1;
            while (addend[2] != -1) {
                addend[2] = nextPrime(addend[2]);
                if (addend[2] == -1) break;
                addend[3] = partialSum - addend[2];
                if (addend[3] < 2) break;

                if (addend[3] >= PRIME_MAX) {
                    addend[2] = partialSum - PRIME_MAX;
                    continue;
                }
                if (isPrime[addend[3]]) return 0;
            }
        }
    }

    return -1;
}

// ----------
// findPrimes
// ----------

// array of primality: if isPrime[n] = true, then n is prime
//                     if isPrime[n] = false, then n is composite
void findPrimes() {
  int i, j;
  
    isPrime[0] = isPrime[1] = false;
  for(i = 2; i < PRIME_MAX; i++)
    isPrime[i] = true;
  
    for (i = 2; i < PRIME_MAX; i++) {

        // if this is composite, skip it
        if (!isPrime[i]) continue;

        // if prime, mark all multiples as composite
    for(j = i*2; j < PRIME_MAX; j+=i) {
            isPrime[j] = false;
        }
    }
}

// -----
// tests
// -----

#ifdef TEST
#include "TestCollatz.h"
#endif // TEST

// ----
// main
// ----

/**
 * either runs the tests or runs the program
 */
int main () {
    using namespace std;
    ios_base::sync_with_stdio(false); // turn off synchronization with C I/O
    
#ifdef TEST
    // ----------
    // unit tests
    // ----------
    
    CppUnit::TextTestRunner tr;
    tr.addTest(TestCollatz::suite());
    tr.run();
#else
    // -------
    // program
    // -------
    
    findPrimes();

    while (read(cin)) {
        if (sum < 8) {
            cout << "Impossible." << endl;
        } else {
            if (eval() == 0) {
                print(cout);
            } else {
                return 1;
            }
        }
    }

#endif // TEST
    
    return 0;
}
